#include<iostream>
#include<time.h>

const int capacity = 10; 

class MinHeap 
{
private:
   
    
    int GetParent(int i){return (i-1)/2 ;}
    int GetLeftChild(int i){return 2 * i + 1;}
    int GetRightChild(int i){return 2 * i + 2;}

    void SiftUp( int i )  // 上浮操作
    {
        while( i > 0 && array[i] < array[GetParent(i)])
        {
            std::swap(array[i],array[GetParent(i)]);
            i = GetParent(i);
        }
    } 
    
    void SiftDown(int i)  // 下沉操作
    {
        int leftchild = GetLeftChild(i);
        int rightchild = GetRightChild(i);

        int Min = i;
        
        if(leftchild < size && array[leftchild] < array[i])// 判断左孩子下标是否存在 同时 左孩子是否比我小
        {
            Min  = leftchild;       //左孩子比我小，那么左孩子就是最小根
        }
        if(rightchild < size && array[rightchild] < array[Min])//判断右孩子下标是否存在 同时右孩子是否比 最小根 小
        {
            Min = rightchild;       //右孩子比最小根小，那么右孩子就是最小根
        }

        if(Min != i)
        {
            std::swap(array[i],array[Min]);
            SiftDown(Min);
        }
    }
    
    int array[capacity]; //一个数组用来装 序号
    int size;  //数组当前的元素个数



public:
    MinHeap():size(0){};

    void Insert(int value)
    {
        array[size] = value;
        SiftUp(size);
        size++;
    }
    


    //删除根
    void RemoveRoot()
    {
        if(size == 0)
            return;
        array[0] = array[--size];//把最新的值变成根，然后下沉
        SiftDown(0);
    }

    int& GetRoot()
    {
        return array[0];
    }

    void show()
    {
        for(int i = 0 ; i < size;i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }



};









int main()
{
    // MinHeap h;
    // for(int i=0;i<10;i++)
    // {
    //     h.Insert(i+1);
    // }

    // h.show();

    // h.RemoveRoot();

    // h.show();

    srand(time(nullptr));
    int a[20];

    for(int i=0;i<20;i++)
    {
        a[i] = rand()%100 + 1;//生成 1 - 100 之间的随机数  
    }
    for(int i=0;i<20;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    MinHeap h;
    for(int i=0;i<20;i++)
    {
        if(i < 5)
        {
            h.Insert(a[i]);
        }
        
        if(a[i] > h.GetRoot())
        {
            h.RemoveRoot();
            h.Insert(a[i]);
        }
    }

    h.show();

    return 0;
}